#define _CRT_SECURE_NO_WARNINGS	

int searchInsert(int* nums, int numsSize, int target)
{
    if (nums[0] > target)
        return 0;
    if (nums[numsSize - 1] < target)
        return numsSize;
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (target == nums[mid])
            return mid;
        else if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}